package demo13;

import javafx.util.Pair;

import java.util.Arrays;


class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
}

public class Solution {

    //1.不相交的线(动态规划)
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int[][] dp = new int[len1 + 1][len2 + 1];
        int result = 0;
        for(int i = 1; i <= len1; i++) {
            for(int j = 1; j <= len2; j++) {
                if(nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
                if(dp[i][j] > result) {
                    result = dp[i][j];
                }
            }
        }
        return result;
    }

    //2.最大子数组和(动态规划)
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len];
        dp[0] = nums[0];
        int result = nums[0];
        for(int i = 1; i < len; i++) {
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            if(result < dp[i]) {
                result = dp[i];
            }
        }
        return result;
    }

    //3.判断子序列(动态规划)
    public boolean isSubsequence(String s, String t) {
        int len1 = s.length();
        int len2 = t.length();
        int[][] dp = new int[len1 + 1][len2 + 1];
        for(int i = 1; i <= len1; i++) {
            for(int j = 1; j <= len2; j++) {
                if(s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = dp[i][j - 1];
                }
            }
        }
        return dp[len1][len2] == s.length();
    }

    //4.不同的子序列(动态规划)
    public int numDistinct(String s, String t) {
        int len1 = s.length();
        int len2 = t.length();
        int[][] dp = new int[len1 + 1][len2 + 1];
        //初始化
        for(int i = 0; i <= len1; i++) {
            dp[i][0] = 1;
        }
        //递推
        for(int i = 1; i <= len1; i++) {
            for(int j = 1; j <= len2; j++) {
                if(s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[len1][len2];
    }
//
//    //5.两个字符串的删除操作(动态规划)
//    public int minDistance(String word1, String word2) {
//        int len1 = word1.length();
//        int len2 = word2.length();
//        int[][] dp = new int[len1 + 1][len2 + 1];
//        for(int i = 0; i <= len1; i++) {
//            dp[i][0] = i;
//        }
//        for(int j = 0; j <= len2; j++) {
//            dp[0][j] = j;
//        }
//        for(int i = 1; i <= len1; i++) {
//            for(int j = 1; j <= len2; j++) {
//                if(word1.charAt(i - 1) == word2.charAt(j - 1)) {
//                    dp[i][j] = dp[i - 1][j - 1];
//                } else {
//                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;
//                }
//            }
//        }
//        return dp[len1][len2];
//    }

    //6.编辑距离(动态规划)
    public int minDistance(String word1, String word2) {
        int len1 = word1.length();
        int len2 = word2.length();
        int[][] dp = new int[len1 + 1][len2 + 1];
        //初始化
        for(int i = 0; i <= len1; i++) {
            dp[i][0] = i;
        }
        for(int j = 0; j <= len2; j++) {
            dp[0][j] = j;
        }
        //递推
        for(int i = 1; i <= len1; i++) {
            for(int j = 1; j <= len2; j++) {
                if(word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    //增加删除
                    int addDel = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;
                    //替换
                    int replace = dp[i - 1][j - 1] + 1;
                    dp[i][j] = Math.min(addDel, replace);
                }
            }
        }
        return dp[len1][len2];
    }

    //7.回文子串(动态规划)
    public int countSubstrings(String s) {
        int len = s.length();
        boolean[][] dp = new boolean[len][len];
        int result = 0;
        for(int i = len - 1; i >= 0; i--) {
            for(int j = i; j < len; j++) {
                if(s.charAt(i) == s.charAt(j)) { //左右两端字符相等
                    if(j - i <= 1) { //区间长度小于等于1
                       dp[i][j] = true;
                       result++;
                    } else if(dp[i + 1][j - 1]) { //中间是回文串
                        dp[i][j] = true;
                        result--;
                    }
                }
            }
        }
        return result;
    }

    //8.最长回文子序列(动态规划)
    public int longestPalindromeSubseq(String s) {
        int len = s.length();
        int[][] dp = new int[len][len];
        //初始化
        for(int i = 0; i < len; i++) {
            dp[i][i] = 1;
        }
        //递推
        for(int i = len - 1; i >= 0; i--) {
            for(int j = i; j < len; j++) {
                if(s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;//两端的元素都考虑
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);//两端元素只考虑最大的
                }
            }
        }
        return dp[0][len - 1];
    }

//    //9.打家劫舍(三刷)
//    public int rob(int[] nums) {
//        int len = nums.length;
//        if(len == 1) return nums[0];
//        if(len == 2) return Math.max(nums[0], nums[1]);
//        int[] dp = new int[len];
//        dp[0] = nums[0];
//        dp[1] = Math.max(nums[0], nums[1]);
//        for(int i = 2; i < len; i++) {
//            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
//        }
//        return dp[len - 1];
//    }

    //10.打家劫舍II(二刷)
    public int rob(int[] nums) {
        int len = nums.length;
        if(len == 1) return nums[0];
        if(len == 2) return Math.max(nums[0], nums[1]);
        int first = robI(Arrays.copyOfRange(nums, 0, len - 1));
        int last = robI(Arrays.copyOfRange(nums, 1, len));
        return Math.max(first, last);
    }

    private int robI(int[] nums) {
        int len = nums.length;
        if(len == 1) return nums[0];
        if(len == 2) return Math.max(nums[0], nums[1]);
        int[] dp = new int[len];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for(int i = 2; i < len; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }

        return dp[len - 1];
    }

    //打家劫舍III(二刷)
    public int rob(TreeNode root) {
        Pair<Integer, Integer> dp = dfs(root);
        return Math.max(dp.getKey(), dp.getValue());
    }

    private Pair<Integer, Integer> dfs(TreeNode root) {
        if(root == null) {
            return new Pair<>(0, 0);
        }
        Pair<Integer, Integer> dpLeft = dfs(root.left);
        Pair<Integer, Integer> dpRight = dfs(root.right);
        int val1 = Math.max(dpLeft.getKey(), dpLeft.getValue()) +
                Math.max(dpRight.getValue(), dpRight.getKey());//不偷当前结点
        int val2 = dpLeft.getKey() + dpRight.getKey() + root.val;//偷当前结点
        return new Pair<>(val1, val2);
    }



}

class Main {
    public static void main(String[] args) {
        String arr1 = "aaa";
        Solution solution = new Solution();
        solution.countSubstrings(arr1);
    }
}
